package com.dyz.leetcode;

/**
 * @author: daiyizheng
 * @date: 2021/7/2 22:30
 * @description:
 */
public class MaxSubArray53 {
    public static void main(String[] args) {

    }
    //暴力解法
    public int maxSubArray(int[] nums) {
        if(nums==null||nums.length==0){return 0;}
        int max = Integer.MIN_VALUE;
        for (int s=0;s<nums.length;s++){
            int sum = 0;
            for(int e = s;e<nums.length;e++){
                sum+=nums[e];
                max = Math.max(sum, max);
            }
        }
        return max;
    }
    // 方法二 动态规划
    // f(i)表示以第i个数字结尾的[连续子数组的最大和」，很显然我们要求的答案就是：max[f(i) for i in range(n)]
    // 状态转移方程为：f(i)=max(f(i-1)+nums]，nums])
    public int maxSubArray1(int[] nums) {
        if(nums==null||nums.length==0){return 0;}
        int [] dp = new int[nums.length+1];
        int max = nums[0];
        dp[0] = nums[0];
        for (int i=1; i<nums.length;i++){
            dp[i] = Math.max(dp[i-1]+nums[i], nums[i]);
            max = Math.max(dp[i], max);
        }
        return max;
    }


    //方法三：在线处理 https://www.bilibili.com/video/BV1UT4y1w7ZG
    public int maxSubArray2(int[] nums) {
        int max = Integer.MIN_VALUE, sum=0;

        //遍历
        for(int i =0;i<nums.length;i++){
            sum +=nums[i];
            if(sum>max){max=sum;}
            if(sum<0){sum=0;}
        }

        return max;

    }
}
